import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

public class Agent
{
	private Boolean fileLoaded = false;
	public Node ID3_Tree = null;
	private HashMap<String, Integer> attributs = new HashMap<String, Integer>();

	public Agent(String examplesFilePath)
	{
		if (this.generateExamples(examplesFilePath))
		{
			fileLoaded = true;
		}
	}

	private Boolean generateExamples(String examplesFilePath)
	{
		FileInputStream fstream = null;
		ArrayList<String[]> examples = new ArrayList<String[]>();
		String targetAttribut = null;
		ArrayList<String> nonTargetAttributs = new ArrayList<String>();
		try
		{
			fstream = new FileInputStream(examplesFilePath);
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String strLine;
			int ctr = 0;
			while ((strLine = br.readLine()) != null)
			{
				if (ctr == 0)
				{
					String[] attributsList = strLine.split(";");
					for (int i = 0; i < attributsList.length; ++i)
					{
						if (i + 1 == attributsList.length)
						{
							targetAttribut = attributsList[i];
						}
						else
						{
							nonTargetAttributs.add(attributsList[i]);
						}
						attributs.put(attributsList[i], i);
					}
				}
				else
				{
					examples.add(strLine.split(";"));
				}
				++ctr;
			}
			in.close();
			this.ID3_Tree = this.ID3(examples, targetAttribut,
					nonTargetAttributs);

			return true;
		}
		catch (FileNotFoundException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		catch (IOException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return false;
	}

	private Node ID3(ArrayList<String[]> examples, String targetAttribut,
			ArrayList<String> nonTargetAttribut)
	{
		String uniqueTarget = null;
		if (examples.size() == 0)
		{
			return null;
		}
		else if (nonTargetAttribut.size() == 0)
		{
			HashMap<String, Integer> nbTargetList = new HashMap<String, Integer>();
			ArrayList<String> targetPossible = new ArrayList<String>();
			for (int i = 0; i < examples.size(); ++i)
			{
				int lastElementIndex = examples.get(i).length - 1;
				if (nbTargetList.containsKey(examples.get(i)[lastElementIndex]))
				{
					nbTargetList
							.put(examples.get(i)[lastElementIndex],
									nbTargetList.get(examples.get(i)[lastElementIndex]) + 1);
				}
				else
				{
					nbTargetList.put(examples.get(i)[lastElementIndex], 0);
					targetPossible.add(examples.get(i)[lastElementIndex]);
				}
			}
			String mostTarget = "";
			int nbMax = -1;
			for (int i = 0; i < targetPossible.size(); ++i)
			{
				if (nbTargetList.get(targetPossible.get(i)) > nbMax)
				{
					nbMax = nbTargetList.get(targetPossible.get(i));
					mostTarget = targetPossible.get(i);
				}
			}
			return new Node(mostTarget);
		}
		else if ((uniqueTarget = testIfallSameValue(examples)) != null)
		{
			return new Node(uniqueTarget);
		}
		else
		{
			int selectedAttrPos = this.bestGain(examples, nonTargetAttribut);
			
			if (selectedAttrPos < 0)
			{
				Node newNode = new Node(examples.get(-(selectedAttrPos + 1))[examples.get(0).length - 1]);
				return newNode;
			}

			Node newNode = new Node(nonTargetAttribut.get(selectedAttrPos));
			
			HashMap<String, Integer> values = new HashMap<String, Integer>();
			for (int i = 0; i < examples.size(); ++i)
			{
				values.put(examples.get(i)[selectedAttrPos], 0);
			}
			Set<String> keys = values.keySet();
			for (String key : keys)
			{
				Node tmpNode = new Node(key);
				ArrayList<String[]> filteredExamples = filterExamplesWithValueAttr(
						examples, selectedAttrPos, key);
				tmpNode.addNode(this.ID3(filteredExamples, targetAttribut,
						nonTargetAttribut));
				newNode.addNode(tmpNode);

			}
			return newNode;
		}
	}

	private int bestGain(ArrayList<String[]> examples,
			ArrayList<String> nonTargetAttribut)
	{
		ArrayList<HashMap<String, Integer[]>> countAttr = new ArrayList<HashMap<String, Integer[]>>();
		for (int i = 0; i < examples.size(); ++i)
		{
			String[] exemple = examples.get(i);
			for (int j = 0; j < exemple.length; ++j)
			{
				if (i == 0)
				{
					countAttr.add(new HashMap<String, Integer[]>());
				}
				if (countAttr.get(j).containsKey(exemple[j]))
				{
					Integer[] counts = new Integer[2];
					counts[0] = countAttr.get(j).get(exemple[j])[0] + 1;
					if (exemple[exemple.length - 1].equals(examples.get(0)[examples.get(0).length - 1]))
					{
						counts[1] = countAttr.get(j).get(exemple[j])[1] + 1;
					}
					else
					{
						counts[1] = countAttr.get(j).get(exemple[j])[1];
					}
					countAttr.get(j).put(exemple[j], counts);
				}
				else
				{
					Integer[] counts = new Integer[2];
					counts[0] = 1;
					if (j == exemple.length - 1)
					{
						counts[1] = i;
					}
					else if (exemple[exemple.length - 1].equals(examples.get(0)[examples.get(0).length - 1]))
					{
						counts[1] = 1;
					}
					else
					{
						counts[1] = 0;
					}
					countAttr.get(j).put(exemple[j], counts);
				}
			}
		}
		ArrayList<Double> gainList = new ArrayList<Double>();
		
		double entDec = 0.0;
		countAttr.get(countAttr.size() - 1).keySet();
		Set<String> keysDec = countAttr.get(countAttr.size() - 1).keySet();
		entDec = entropy(countAttr.get(countAttr.size() - 1), keysDec);
		int pos = -1;
		int cnt = 0;
		for (String key : keysDec)
		{
			if (cnt < countAttr.get(countAttr.size() - 1).get(key)[0])
			{
				cnt = countAttr.get(countAttr.size() - 1).get(key)[0];
				pos = pos - countAttr.get(countAttr.size() - 1).get(key)[1];
			}
		}
		
		for (int i = 0; i + 1 < countAttr.size(); ++i)
		{
			countAttr.get(i).keySet();
			Set<String> keys = countAttr.get(i).keySet();

			gainList.add(entDec);
			for (String key : keys)
			{
				gainList.set(i, gainList.get(i) - ((double)countAttr.get(i).get(key)[0] / examples.size()) *
						entropy(countAttr.get(i).get(key)));
			}
		}
		double tmp = 0.0;
		double high = 0.0;
		for (int i = 0; i < gainList.size(); ++i)
		{
			tmp = gainList.get(i);
			if (high < tmp)
			{
				high = tmp;
				pos = i;
			}
		}
		return pos;
	}

	private double entropy(Integer[] counts)
	{
		double ent = 0.0;
		double countTrue = (double)counts[1];
		double countTotal = (double)counts[0];
		
		ent = -(countTrue / countTotal) * log2(countTrue / countTotal) - 
				((countTotal - countTrue) / countTotal) * log2((countTotal - countTrue) / countTotal);
		return ent;
	}
	
	private double entropy(HashMap<String, Integer[]> countAttr, Set<String> keys)
	{
		double ent = 0.0;
		double countTrue = 0.0;
		double countTotal = 0.0;
		
		for (String key : keys)
		{
			countTrue = (double)countAttr.get(key)[0];
			countTotal = countTotal + (double)countAttr.get(key)[0];
		}
		
		ent = - (countTrue / countTotal) * log2(countTrue / countTotal) - 
				((countTotal - countTrue) / countTotal) * log2((countTotal - countTrue) / countTotal);
		
		return ent;
	}
	
	private double log2(double a)
	{
		if (a == 0)
		{
			return 0;
		}
		else
		{
			return Math.log(a) / Math.log(2);
		}
	}

	private ArrayList<String[]> filterExamplesWithValueAttr(
			ArrayList<String[]> examples, int selectedAttrPos, String value)
	{
		ArrayList<String[]> newExamples = new ArrayList<String[]>();

		for (int i = 0; i < examples.size(); ++i)
		{
			if (examples.get(i)[selectedAttrPos].equals(value))
			{
				newExamples.add(examples.get(i));
			}
		}

		return newExamples;
	}

	private String testIfallSameValue(ArrayList<String[]> examples)
	{
		String targetTmpAttr = null;
		for (int i = 0; i < examples.size(); ++i)
		{
			int lastElementIndex = examples.get(i).length - 1;
			if (targetTmpAttr == null)
			{
				targetTmpAttr = examples.get(i)[lastElementIndex];
			}
			else if (targetTmpAttr != examples.get(i)[lastElementIndex])
			{
				return null;
			}
		}
		return targetTmpAttr;
	}

	public Boolean getFileLoaded()
	{
		return fileLoaded;
	}
}
